package binarysearch

//搜索插入位置  若存在 返回位置，若不存在，返回插入位置
func searchInsert(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}
	left,right := 0,len(nums)-1   // 左闭右闭
	for left<=right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}else if nums[mid]<target{
			left = mid+1
		}else{
			right = mid-1
		}
	}
	// 如果没有返回，说明没有找到目标值
	// 插入位置为left
	return left
}
